/*
 * optibiparti.cpp
 *
 *  Created on: 10 nov. 2011
 *      Author: pmilian
 */

#include "algo.h"

int
nextUnseen(vector <bool> v) {
	unsigned i;
	for (i = 0; i < v.size(); ++i) {
		if (!v.at(i)) {
			return i;
		}
	}
	return -1;
}

int getNextVertex(vector<int> color) {
	unsigned i;
	for (i = 0; i < color.size(); ++i) {
		if (color[i] == -1) {
			return i;
		}
	}
	return -1;
}

void
colorize(const Graph *graph, int vertex, vector<int> &color, int currentColor) {
	vector<int> neighbours = graph->getNeighbours(vertex);
	color[vertex] = currentColor;
	int nextColor = currentColor ^ 1;
	unsigned i;

	for (i = 0; i < neighbours.size(); ++i) {
		if (color[neighbours[i]] == -1) {
			colorize(graph, neighbours[i], color, nextColor);
		}
	}
}


vector<int> biparti2approche(const Graph *graph) {
	vector<int> color(graph->getNbVertex(), -1);

	int nextVertex;
	while ((nextVertex = getNextVertex(color)) != -1 ) {
		colorize(graph, nextVertex, color, 0);
	}

	vector<int> colorsArray[2];
	unsigned i;
	for (i = 0; i < color.size(); ++i) {
		colorsArray[color[i]].push_back(i);
	}

	return colorsArray[0].size() > colorsArray[1].size() ? colorsArray[1] : colorsArray[0];
}



